class Solution493 {
    int[] arr  ;
    public int reversePairs(int[] nums) {
        arr = new int[nums.length] ;
        return  merge(nums , 0 , nums.length-1) ;
    }
    private int merge(int[] nums , int left , int right){
        if(left >= right) return 0 ;
        int sum = 0 ;
        int mid = left + (right-left)/2 ;
        sum += merge(nums , left , mid) ;
        sum += merge(nums , mid+1 , right) ;
        int l = left , r = mid+1 ;
        //1. 先找有多少个 翻转对
        while(l <= mid){
            while(r <= right && nums[r] >= nums[l]/2.0){  // r*2 可能会超出int的 , 所以用 l/2.0 , 同时要2.0 小数,
                r ++ ;                                      // 否则出现 3 > 1*2 ==>除以一个整数2 ==>  3/2==1 <= 1 ;所以需要小数
            }
            if(r > right) break ; // 如果r 遍历完了都没有一个 l > r*2 那么直接break (优化)
            sum += right-r+1 ;   // 找到 l > r*2
            l ++ ;            // 同时让 l++
        }
        //2. 找完了翻转对, 在进行 降序排序 ;
        l = left  ; r = mid+1;
        int i = left ;
        while(l <= mid && r <= right){
            if(nums[l] > nums[r]){
                arr[i++] = nums[l++] ;
            }else{
                arr[i++] = nums[r++] ;
            }
        }
        while(l <= mid){
            arr[i++] = nums[l++] ;
        }
        while(r <= right){
            arr[i++] = nums[r++] ;
        }
        for(int j=left ; j <= right ; j ++){
            nums[j] = arr[j];
        }
        return sum ;

    }
}